# !/usr/bin/env python
# -*- coding: utf-8 -*-

'''
# A* Shortest Path Algorithm:
# http://en.wikipedia.org/wiki/A*
# Adriano Leal
# 11951
'''

import math
import image


class AStar(object):
    '''
    Classe AStar contem o algoritimo para pesquisa do menor caminho entre dois pontos.
    Contém os métodos auxiliares do algoritimo A*, metodo de custo e de heiristica.
    '''
    op = None

    def __init__(self):
        self.op = image.OpenImage
        self.P1 = (192, 48)  # P1 = Ponto inicial.
        self.P2 = (260, 508)  # P2 = Ponto final.


    def movimentCost(self, node):
        '''
        A função que recebe dois pontos como argumentos
        e retorna o custo numérico.
        @param node = Ponto com as coordenadas x, y.
        @return = retorna o custo do movimento.
        '''
        return 1 - (self.img[node[1], node[0]][0] / 255.0)


    def heuristic(self, start, goal):
        '''
        Uma função que recebe um ponto de saida e um ponto de meta,
        e retorna a estimativa heurística numérica
        o custo de alcançar o objetivo do ponto.
        @param start = Ponto com a coordenada x, y inicial.
        @param goal = Ponto com a coordenada x, y final.
        @return = retorna o resultado do calculo da heuristica.
        '''
        xd = goal[0] - start[0]
        yd = goal[1] - start[1]
        # Euclidian Distance
        d = math.sqrt(xd * xd + yd * yd)
        return (d)


    def neighbor(self, current, dirs):
        '''
        Gera o número de possíveis direções transitáveis.
        @param current = Ponto com a coordenada x, y atual.
        @param dirs = Direções possiveis a serem seguidas.
        @return = retorna os vizinhos do ponto corrente.
        '''
        dirs = dirs  # número de direções possiveis.

        if dirs == 4:
            dx = xrange(-1, 2)
            dy = xrange(-1, 2)
            # dx = [1, 0, -1, 0]
            # dy = [0, 1, 0, -1]

        elif dirs == 8:
            dx = [1, 1, 0, -1, -1, -1, 0, 1]
            dy = [0, 1, 1, 1, 0, -1, -1, -1]

        neighbor = [(current[0] + x, current[1] + y)
                    for x in dx
                    for y in dy
                    if ((current[0] + x, current[1] + y)
                        not in closeSet)]
        return neighbor


    def aStar(self, dirs, P2):
        '''
        Calcula um caminho mais curto.
        Inicializar o objeto e, em seguida, repetidamente para se
        obter o caminho entre um ponto de partida e um ponto final.
        #Pseudo-código de A *
        #http://wiki.gamegardens.com/Path_Finding_Tutorial#Pathfinding_Overview
        @param dirs = Direções possiveis a serem seguidas.
        @return = retorna a lista fechada com os nós já pesquisados.
        '''
        global closeSet
        # Seta current com o nó inicial
        current = self.P1
        # criar a lista aberta de nós, contendo apenas o nosso nó inicial
        openSet = [self.P1]
        # criar a lista fechada de nós, inicialmente vazia
        closeSet = []
        # enquanto não for atingido o nosso objetivo
        while not (current == P2):
            cost = []
            # calcula o custo do nó contido na lista aberta, adicionando
            # em current o nó com o custo de valor mínimo.
            for node in openSet:
                cost.append(self.movimentCost(node) + self.heuristic(node, P2) / 20)
            current = openSet[cost.index(min(cost))]
            # move o nó atual para a lista fechada
            openSet.remove(current)
            closeSet.append(current)
            # adiciona na lista aberta os vizinhos do nó corrente.
            if current not in openSet:
                openSet = self.neighbor(current, dirs)
        return closeSet


